from collections import Counter
from typing import List


# 438. 找到字符串中所有字母异位词
def findAnagrams(s: str, p: str) -> List[int]:
    s_len = len(s)
    # 字符串 p 一些信息
    p_dict = dict(Counter(p))
    p_len = len(p)

    re = list()
    word_count = 0
    start_index = 0
    window_dict = {}
    while start_index < s_len:
        current_char = s[start_index]
        current_char_count = window_dict.get(current_char, 0)
        window_dict[current_char] = current_char_count + 1
        word_count += 1

        if word_count > p_len:
            del_index = start_index - p_len
            del_char = s[del_index]
            del_char_count = window_dict.get(del_char)
            if del_char_count == 1:
                window_dict.pop(del_char)
            else:
                window_dict[del_char] -= 1
            word_count -= 1

        if word_count == p_len:
            if window_dict == p_dict:
                re.append(start_index - p_len + 1)

        start_index += 1

    return re


s_1 = "cbaebabacd"
p_1 = "abc"
result = findAnagrams(s_1, p_1)
print(f"result:{result}")

s_1 = "abab"
p_1 = "ab"
result = findAnagrams(s_1, p_1)
print(f"result:{result}")
